package com.gitee.feizns.explore.data_structure.tree.bs.easy;

/**
 * @author feizns
 * @since 2019/12/24
 */
public class SortedArrayToBST {

    public static void main(String[] args) {
        int[] tmp = {1,2,3,4,5,6,7,8,9,10};
        TreeNode node = sortedArrayToBST(tmp);
    }

    public static TreeNode sortedArrayToBST(int[] num) {
        return create(num, 0, num.length - 1);
    }

    private static TreeNode create(int[] num, int start, int end) {
        if ( start <= end ) {
            int mid = (start + end) / 2;
            TreeNode ret = new TreeNode(num[mid]);
            ret.left = create(num, start, mid - 1);
            ret.right = create(num, mid + 1, end);
            return ret;
        }
        return null;
    }

//    public static TreeNode sortedArrayToBST(int[] num) {
//        int mid = num.length / 2;
//        TreeNode ret = new TreeNode(num[mid]);
//        for (int i = 0; i < num.length; i++)
//            ret = put(ret, num[i]);
//        return ret;
//    }
//
//    private static TreeNode put(TreeNode node, int val) {
//        if ( node != null ) {
//            if ( val < node.val ) {
//                node.left = put(node.left, val);
//            } else if ( val > node.val )
//                node.right = put(node.right, val);
//            int lh = h(node.left);
//            int rh = h(node.right);
//            int balance = lh - rh;
//            if ( balance > 1 )
//                node = rightRotate(node);
//            else if ( balance < -1 )
//                node = leftRotate(node);
//            return node;
//        }
//        return new TreeNode(val);
//    }
//
//    private static int h(TreeNode node) {
//        return node == null ? 0 : Math.max(h(node.left), h(node.right)) + 1;
//    }
//
//    private static TreeNode rightRotate(TreeNode node) {
//        TreeNode left = node.left;
//        node.left = left.right;
//        left.right = node;
//        return left;
//    }
//
//    private static TreeNode leftRotate(TreeNode node) {
//        TreeNode right = node.right;
//        node.right = right.left;
//        right.left = node;
//        return right;
//    }

}
